package com.dh.leetcode.k1;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * ClassName: _1926_nearest_exit_from_entrance_in_maze
 *
 * @author shouzimu
 * @Description: 1926. 迷宫中离入口最近的出口
 * 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
 *
 * 每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
 *
 * 请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
 * 输出：1
 * 解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
 * 一开始，你在入口格子 (1,2) 处。
 * - 你可以往左移动 2 步到达 (1,0) 。
 * - 你可以往上移动 1 步到达 (0,2) 。
 * 从入口处没法到达 (2,3) 。
 * 所以，最近的出口是 (0,2) ，距离为 1 步。
 * 示例 2：
 *
 *
 * 输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
 * 输出：2
 * 解释：迷宫中只有 1 个出口，在 (1,2) 处。
 * (1,0) 不算出口，因为它是入口格子。
 * 初始时，你在入口与格子 (1,0) 处。
 * - 你可以往右移动 2 步到达 (1,2) 处。
 * 所以，最近的出口为 (1,2) ，距离为 2 步。
 * 示例 3：
 *
 *
 * 输入：maze = [[".","+"]], entrance = [0,0]
 * 输出：-1
 * 解释：这个迷宫中没有出口。
 *
 * https://leetcode-cn.com/problems/nearest-exit-from-entrance-in-maze/
 *
 *
 * @date 2022/2/6 12:08
 */
public class _1926_nearest_exit_from_entrance_in_maze {

    public int nearestExit(char[][] maze, int[] entrance) {
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int m = maze.length, n = maze[0].length;
        int x = entrance[0], y = entrance[1];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, y});
        Map<Integer, Integer> stepMap = new HashMap<>();
        stepMap.put(x * m + y, 0);
        while (!queue.isEmpty()) {
            int[] xy = queue.poll();
            int dx = xy[0];
            int dy = xy[1];
            int step = stepMap.get(dx * m + dy);
            if ((dx != x || dy != y) && (dx == 0 || dx == m - 1 || dy == 0 || dy == n - 1)) {
                return step;
            }
            for (int[] dir : dirs) {
                int nx = dx + dir[0], ny = dy + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || maze[nx][ny] == '+') {
                    continue;
                }
                int key = nx * m + ny;
                if (stepMap.containsKey(key)) {
                    continue;
                }
                stepMap.put(nx * m + ny, step + 1);
                queue.add(new int[]{nx, ny});
            }
        }
        return -1;
    }

    @Test
    public void nearestExitTest() {
        Assert.assertEquals(1, nearestExit(new char[][]{{'.'}, {'.'}, {'.'}, {'.'}}, new int[]{2, 0}));
        Assert.assertEquals(-1, nearestExit(new char[][]{{'.', '+'}}, new int[]{0, 0}));
        Assert.assertEquals(1, nearestExit(new char[][]{{'+', '+', '.', '+'}, {'.', '.', '.', '+'}, {'+', '+', '+', '.'}}, new int[]{1, 2}));
        Assert.assertEquals(2, nearestExit(new char[][]{{'+', '+', '+'}, {'.', '.', '.'}, {'+', '+', '+'}}, new int[]{1, 0}));
    }
}
